package pfq.demo.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序:
 * <p>
 * 每次将后面待排序的元素插入到前面排好序的数组中
 * <p>
 * 时间复杂度
 * 最好：O(n)
 * 最坏：O(n^2)
 * 平均：O(n^2)
 */
public class InsertSort {

    public static void main(String[] args) {

        int[] data = Arrays.copyOf(Utils.data(), Utils.data().length);
        System.out.println("排序前：" + Arrays.toString(data));
        insertSort(data);
        System.out.println("排序后：" + Arrays.toString(data));

    }


    /**
     * 插入数据，要将数据向后移动后才能插入
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {

            int value = arr[i];

            int j = i - 1;

            for (; j >= 0; j--) {

                if (arr[j] > value) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }

            arr[j + 1] = value;
        }
    }


}
